<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        class Tree {
            constructor(data) {
                this.data = data; // 数据域
                this.left = null; // 左指针域
                this.right = null; // 右指针域
                // 记录当前二叉节点信息
                this.root = this;
            }
        }

        //  操作二叉树的方法
        class BSTerr {
            constructor() {
                // root: 树形结构
                this.root = null
            }

            // 添加二叉树
            // 1.创建树形节点 2.寻找一个合适的位置 插入节点
            insert(data) {
                // 1.创建节点
                const newNode = new Tree(data)

                // 创建一个添加的方法
                const insertNode = (node, newNode) => {
                    // 当前数据域和新数据域比较
                    if (node.data > newNode.data) {
                        if (node.left === null) {
                            node.left = newNode
                        } else insertNode(node.left, newNode)
                    } else if (node.data < newNode.data) {
                        if (node.right === null) {
                            node.right = newNode
                        } else insertNode(node.right, newNode)
                    }
                }

                // 2.寻找一个合适的位置 插入节点
                // 判断 root 树形结构是否为空  如果为空的话 直接插入
                if (this.root === null) {
                    this.root = newNode
                } else {
                    // 不为空就需要找合适的位置
                    insertNode(this.root, newNode)
                }
            }

            // 获取二叉树的最大值
            getMax() {
                // 创建一个获取最大值的方法
                const getMaxNode = (node) => {
                    return node ? (node.right ? getMaxNode(node.right) : node) : null;
                };

                return getMaxNode(this.root)
            }

            // 获取二叉树的最小值
            getMin(node) {
                const getMinNode = (node) => {
                    return node ? (node.left ? getMinNode(node.left) : node) : null;
                };

                return getMinNode(node || this.root)
            }

            // 查找二叉树中某一个确定的值
            search(data) {
                // 创建一个查找的方法
                const searchNode = (node, data) => {
                    // 判断 树是否为空 
                    if (node === null) return null;

                    // 如果当前树的数据域 和 要查找的 数 相同 就返回当前 树
                    if (node.data === data) return node;

                    // 如果当前树的数据域大于要查找的树 就通过递归 查找左指针域
                    if (node.data > data) {
                        return searchNode(node.left, data)
                    } else {
                        // 反之查找右指针域
                        return searchNode(node.right, data)
                    }

                }

                // 返回查找的结果
                return searchNode(this.root, data)
            }

            // 删除节点
            remove(data) {
                // 创建一个删除的方法
                const removeNode = (node, data) => {
                    if (node === null) return null;

                    if (node.data === data) {
                        // 删除操作
                        if (node.left === null && node.right === null) return null;

                        if (node.left === null) return node.right;

                        if (node.right === null) return node.left;

                        if (node.right !== null && node.left !== null) {
                            // 从右指针域中找到最小值，替换当前数据域
                            const _node = getMin(node.right)

                            node.data = _node.data;

                            node.right = removeNode(node.right, _node.data);

                            return node;
                        }
                    } else if (node.data > data) {
                        // 当前的右指针域 等于我删除的结果
                        node.left = removeNode(node.left, data);

                        // 返回结果
                        return node
                    } else {
                        node.right = removeNode(node.right, data);

                        return node
                    }

                };

                removeNode(this.root, data)
            }

            // 前序遍历
            inOrder() {
                    const newArr = [];

                    // 创建遍历的方式
                    const inOrderNode = (node, callback) => {
                        if (node !== null) {
                            newArr.push(callback(node.data))

                            inOrderNode(node.left, callback)

                            inOrderNode(node.right, callback)
                        }
                    };

                    // 临时用来存储当前节点信息
                    const callback = v => v;

                    // 触发遍历的方法
                    inOrderNode(this.root, callback)

                    return newArr
                }
                // 中序遍历
            middleOrder() {
                    const newArr = [];

                    const middleOrderNode = (node, callback) => {
                        if (node !== null) {
                            middleOrderNode(node.left, callback);

                            newArr.push(callback(node.data));

                            middleOrderNode(node.right, callback)
                        }
                    }


                    const callback = v => v;

                    middleOrderNode(this.root, callback)

                    return newArr
                }
                // 后续遍历
            nextOrder() {
                const newArr = [];

                const nextOrderNode = (node) => {
                    if (node !== null) {
                        nextOrderNode(node.left);

                        nextOrderNode(node.right);

                        newArr.push(node.data)
                    }
                };

                nextOrderNode(this.root)

                return newArr
            }
        }

        const myTree = new BSTerr();

        const arr = [10, 8, 12, 6, 9, 11, 15]


        arr.forEach(item => {
            myTree.insert(item)
        })

        console.log(myTree)

        console.log(arr)

        // console.log(myTree.getMax())
        // console.log(myTree.getMin())
        // console.log(myTree.search())
        // myTree.remove(6)

        console.log(myTree.inOrder())
        console.log(myTree.middleOrder())
        console.log(myTree.nextOrder())
    </script>
</body>

</html>